package algotithm.weekendrace.leetcode224.test3;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author zhouyanxiang
 * @Date 2021-01-2021/1/17-23:13
 */
public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[][] matrix = {{0,0,1},{1,1,1},{1,0,1}};
        int submatrix = solution.largestSubmatrix(matrix);
        System.out.println(submatrix);
    }

    public int largestSubmatrix(int[][] matrix) {
        int row = matrix.length, col = matrix[0].length;
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(i > 0){
                    if(matrix[i][j] == 1) {
                        matrix[i][j] += matrix[i - 1][j];
                    }
                }
            }
        }
        List<Integer> list = new ArrayList<>();
        int res = 0;
        for(int i = 0; i < row; i++){
            list.clear();
            for(int j = 0; j < col; j++){
                list.add(matrix[i][j]);
            }
            Collections.sort(list, Collections.reverseOrder());
            int cur = 0;
            for(int j = 0; j < col; j++){
                cur = Math.max((j + 1) * list.get(j), cur);
            }
            res = Math.max(res, cur);
        }
        return res;
    }

}
